﻿#pragma once
#include <iostream>
#include <vector>
using namespace std;
namespace BSTree {
	template <class k>
	struct TreeNode
	{
		k _key = k();
		TreeNode* leftchlid = nullptr;
		TreeNode* rightchlid = nullptr;

		TreeNode(const k& key)
			:_key(key)
			, leftchlid(nullptr)
			, rightchlid(nullptr)
		{}
	};

	template <class T>
	class BSTree {
	public:
		typedef TreeNode<T> BTNode;
		//构造函数
		BSTree() {
			/*BTNode* node = new BTNode;
			node->_key = T();
			node->leftchlid = nullptr;
			node->rightchlid = nullptr;
			root = node;*/
			_root = nullptr;

		}

		//插入
		bool insertTreeNode(const T& val) {
			//如果树为空
			if (_root == nullptr) {
				_root = new BTNode(val);
				return true;
			}
			else {
				BTNode* node = new BTNode(val);
				BTNode* cur = _root;

				while (cur) {
					//比root小往左
					if (val < cur->_key) {

						if (cur->leftchlid == nullptr) {
							cur->leftchlid = node;
							break;
						}

						cur = cur->leftchlid;

					}
					//比root大往右
					else if (val > cur->_key) {

						if (cur->rightchlid == nullptr) {
							cur->rightchlid = node;
							break;
						}

						cur = cur->rightchlid;
					}

					else {
						return false;
					}
				}
				return true;
			}
		}

		//中序遍历
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		//查找
		bool find(const T& val) {
			BTNode* cur = _root;
			while (cur) {

				if (val > cur->_key) {
					cur = cur->rightchlid;
				}

				else if (val < cur->_key) {
					cur = cur->leftchlid;
				}

				//val=cur->_key 找到了
				else {
					return true;
				}

			}
			//cur=null 没找到
			return false;

		}

		//删除
		bool erase(const T& val) {
			//先找到要删的数
			BTNode* cur = _root;
			/*还需要父节点*/
			BTNode* parent = nullptr;
			while (cur) {

				if (val > cur->_key) {
					parent = cur;
					cur = cur->rightchlid;

				}
				else if (val < cur->_key) {
					parent = cur;
					cur = cur->leftchlid;

				}
				//找到了 跳出循环
				else {
					break;
				}
			}
			//cur=null 没找到
			if (cur == nullptr) {
				return false;
			}

			//删除
			 //要删除的结点N左孩⼦位空，右孩⼦结点不为空
			if (cur->leftchlid == nullptr) {
				//如果cur为头节点 parent=nullptr
				if (cur == _root) {
					_root = cur->rightchlid;
				}
				//cur不为头节点
				else {
					//父亲指向我的右
					if (parent->rightchlid == cur) {
						parent->rightchlid = cur->rightchlid;
					}
					//父亲指向我的左
					else if (parent->leftchlid == cur) {
						parent->leftchlid = cur->rightchlid;
					}
				}
				//删除
				delete cur;
				return true;
			}
			//要删除的结点N右孩⼦位空，左孩⼦结点不为空
			else if (cur->rightchlid == nullptr) {
				//如果cur为头节点
				if (cur == _root) {
					_root = cur->leftchlid;
				}

				//如果cur不为头节点
				else {
					if (parent->leftchlid == cur) {
						parent->leftchlid = cur->leftchlid;
					}
					else if (parent->rightchlid == cur) {
						parent->rightchlid = cur->leftchlid;
					}
				}
				//删除
				delete cur;
			}
			//要删除的结点N左右孩⼦结点均不为空
			else {
				//找右子树最小的数
				BTNode* minRight = cur->rightchlid;
				BTNode* minRightParent = cur;//父亲可能为头节点
				while (minRight->leftchlid) {
					minRightParent = minRight;//parent也得变化
					minRight = minRight->leftchlid;
				}
				//用minRight覆盖cur数值
				cur->_key = minRight->_key;
				//调整指针
				if (minRightParent->leftchlid == minRight) {
					minRightParent->leftchlid = minRight->rightchlid;//这里一定是right 
				}
				else {
					minRightParent->rightchlid = minRight->rightchlid;
				}
				//删除
				delete minRight;
			}
		}
	private:

		//中序 左 根 右
		void _InOrder(BTNode* root) {
			if (root == nullptr) {
				return;
			}

			else {
				_InOrder(root->leftchlid);
				cout << root->_key << " ";
				_InOrder(root->rightchlid);
			}
		}
		BTNode* _root;
	};
}
//key_value
namespace key_value {
	template <class k ,class T>
	struct TreeNode
	{
		k _key = k();
		T _val = T();
		TreeNode* leftchlid = nullptr;
		TreeNode* rightchlid = nullptr;

		TreeNode(const k& key,const T& val)
			:_key(key)
			,_val(val)
			, leftchlid(nullptr)
			, rightchlid(nullptr)
		{}
	};

	template <class k ,class T>
	class BSTree {
	public:
		typedef TreeNode<k,T> BTNode;
		//构造函数
		BSTree() {
			/*BTNode* node = new BTNode;
			node->_key = T();
			node->leftchlid = nullptr;
			node->rightchlid = nullptr;
			root = node;*/
			_root = nullptr;

		}

		//插入
		bool insertTreeNode(const k& key ,const T& val) {
			//如果树为空
			if (_root == nullptr) {
				_root = new BTNode(key ,val);
				return true;
			}
			else {
				BTNode* node = new BTNode(key, val);
				BTNode* cur = _root;

				while (cur) {
					//比root小往左
					if (key < cur->_key) {

						if (cur->leftchlid == nullptr) {
							cur->leftchlid = node;
							break;
						}

						cur = cur->leftchlid;

					}
					//比root大往右
					else if (key > cur->_key) {

						if (cur->rightchlid == nullptr) {
							cur->rightchlid = node;
							break;
						}

						cur = cur->rightchlid;
					}

					else {
						return false;
					}
				}
				return true;
			}
		}

		//中序遍历
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		//查找
		BTNode* find(const k& key) {//要传TreeNode* 必须写好模板参数 即TreeNode<k,T>*
			BTNode* cur = _root;
			while (cur) {

				if (key > cur->_key) {
					cur = cur->rightchlid;
				}

				else if (key < cur->_key) {
					cur = cur->leftchlid;
				}

				//val=cur->_key 找到了
				else {
					return cur;
				}

			}
			//cur=null 没找到
			return nullptr;

		}

		//删除
		bool erase(const k& key) {
			//先找到要删的数
			BTNode* cur = _root;
			/*还需要父节点*/
			BTNode* parent = nullptr;
			while (cur) {

				if (key > cur->_key) {
					parent = cur;
					cur = cur->rightchlid;

				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->leftchlid;

				}
				//找到了 跳出循环
				else {
					break;
				}
			}
			//cur=null 没找到
			if (cur == nullptr) {
				return false;
			}

			//删除
			 //要删除的结点N左孩⼦位空，右孩⼦结点不为空
			if (cur->leftchlid == nullptr) {
				//如果cur为头节点 parent=nullptr
				if (cur == _root) {
					_root = cur->rightchlid;
				}
				//cur不为头节点
				else {
					//父亲指向我的右
					if (parent->rightchlid == cur) {
						parent->rightchlid = cur->rightchlid;
					}
					//父亲指向我的左
					else if (parent->leftchlid == cur) {
						parent->leftchlid = cur->rightchlid;
					}
				}
				//删除
				delete cur;
				return true;
			}
			//要删除的结点N右孩⼦位空，左孩⼦结点不为空
			else if (cur->rightchlid == nullptr) {
				//如果cur为头节点
				if (cur == _root) {
					_root = cur->leftchlid;
				}

				//如果cur不为头节点
				else {
					if (parent->leftchlid == cur) {
						parent->leftchlid = cur->leftchlid;
					}
					else if (parent->rightchlid == cur) {
						parent->rightchlid = cur->leftchlid;
					}
				}
				//删除
				delete cur;
			}
			//要删除的结点N左右孩⼦结点均不为空
			else {
				//找右子树最小的数
				BTNode* minRight = cur->rightchlid;
				BTNode* minRightParent = cur;//父亲可能为头节点
				while (minRight->leftchlid) {
					minRightParent = minRight;//parent也得变化
					minRight = minRight->leftchlid;
				}
				//用minRight覆盖cur数值
				cur->_key = minRight->_key;
				//调整指针
				if (minRightParent->leftchlid == minRight) {
					minRightParent->leftchlid = minRight->rightchlid;//这里一定是right 
				}
				else {
					minRightParent->rightchlid = minRight->rightchlid;
				}
				//删除
				delete minRight;
			}
		}
	private:

		//中序 左 根 右
		void _InOrder(BTNode* root) {
			if (root == nullptr) {
				return;
			}

			else {
				_InOrder(root->leftchlid);
				cout << root->_key << " ";
				_InOrder(root->rightchlid);
			}
		}
		BTNode* _root;
	};
}
